/**
 * @file   main.cpp
 * @author ywl <ywl@ywl-VirtualBox>
 * @date   Wed Dec 14 19:10:51 2022
 * 
 * @brief  Bellman-Ford algorithm test program.
 * 
 * 
 */
#include <bits/stdc++.h>
#include <sys/time.h>
#include "Graph.h"
#include <unistd.h>

using namespace std;

int main()
{
    struct timeval t1, t2;
    int vertexNum, edgeNum;
    cin >> vertexNum >> edgeNum;
    Graph g{vertexNum};
    for(int i = 0; i < edgeNum; ++i) {
        int s, e, w;
        cin >> s >> e >> w;
        g.addEdge(s - 1, e - 1, w);
    }
    int s;
    // cout << "Input the start vertex id: ";
    cin >> s;
    gettimeofday(&t1, nullptr);
    g.bellman_ford(s - 1);
    gettimeofday(&t2, nullptr);
    cout << "Cost Time: " << (t2.tv_sec-t1.tv_sec) * 1000000 + t2.tv_usec-t1.tv_usec << "us" << endl;
    return 0;
}
